class Solution
{
public:
    bool have_atl[210][210];
    bool have_pac[210][210];
    int n, m;
    array<int, 2> dxy[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    void dfs(vector<vector<int>> &heights, int x, int y, bool (*st)[210])
    {
        st[x][y] = true;
        int hh = heights[x][y];
        for (auto [dx, dy] : dxy)
        {
            int xx = x + dx, yy = y + dy;
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && heights[xx][yy] >= hh && !st[xx][yy])
            {
                // if(xx == 3 && yy == 0) cout << "dfs!!!\n";
                dfs(heights, xx, yy, st);
            }
        }
    }
    vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights)
    {
        n = heights.size();
        if (!n)
            return {};
        m = heights[0].size();
        for (int i = 0; i < m; ++i)
        {
            // cout << (n - 1) << endl;
            dfs(heights, 0, i, have_pac);
            // cout << "have_atl:\n";
            dfs(heights, n - 1, i, have_atl);
        }
        // cout << have_atl[3][0] << endl;
        for (int i = 0; i < n; ++i)
        {
            dfs(heights, i, 0, have_pac);
            dfs(heights, i, m - 1, have_atl);
        }
        // cout << have_pac[3][0] << ' ' << have_atl[3][0] << endl;
        vector<vector<int>> ans;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (have_atl[i][j] && have_pac[i][j])
                    ans.push_back({i, j});
        return ans;
    }
};